package com.xuwei.base.sort;
/**
  堆排序
  堆的定义：
 n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆：
 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
  性质：
  堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，
  均指该数据结构的这种实现。这种数据结构具有以下性质。任意节点小于它的所有后裔，最小元在堆的根上（堆序性）。
  堆总是一棵完全树。
  将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
 * @author David
 */
public class HeapSort {
	
	public void heapSort(Object[] r) {
		int n=r.length-1;
		for(int i=n/2;i>=1;i--)//初始化堆
			heapAdjust(r,i,n);
		for(int i=n;i>1;i--){  //不断输出堆顶元素并调整r[l...i-1]为新堆
			Object temp=r[1]; //交换堆顶与堆底元素
			r[1]=r[i];
			r[i]=temp;
			heapAdjust(r, 1, i-1); //调整
		}
	}
	
	/**
	 * 数据元素数组r，数组r的待调整区间[low...high]
	 * 调整r[low...high]使之成为大顶堆	 * 
	 */
	//已知r[low...high]中除r[low]之外，其余元素均满足堆的定义
	public void heapAdjust(Object[] r,int low,int high){
		Object temp=r[low];
		//沿关键字较大的元素向下进行筛选
		for(int j=2*low;j<=high;j=j*2){
			//j指向关键字较大的元素
			if(j<high&&compare(r[j],r[j+1])<0) j++;
			//若temp比其孩子都大，则插入到low所指位置
			if(compare(temp, r[j])>=0) break;
			r[low]=r[j];low=j;//向下筛选
		}
		r[low]=temp;		
	}
	

	public static int compare(Object obj1, Object obj2) {
		if((Integer)obj1<(Integer)obj2){
			return -1;
		}else if((Integer)obj1==(Integer)obj2){
			return 0;
		}else{
			return 1;
		}
	}
	
	
	public static void main(String args[]){
		//注意数组中第一个元素（r[0]）不满足堆的定义，不参与排序
		Integer r[]={28,26,17,36,20,42,11,53};		
		//排序前
		for(int i=1;i<r.length;i++){
			System.out.print(r[i]+"--");
		}
		System.out.println();
		new HeapSort().heapSort(r);		
		//排序后
		for(int i=1;i<r.length;i++){
			System.out.print(r[i]+"--");
		}
	}
	

}
